package com.tangyuan.leetcode;

/**
 * @CLASSNAME:
 * @AUTHOR: fenghongyu
 * @TIME: 2021/1/4 19:56
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _92 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        //终止条件
        if(m == 1) {
            //相当于 反转前n 个节点
            return reverseN(head, n);
        }

        //处理当前层
        //// 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, m-1, n-1);
        return head;
    }

    ListNode lastNext = null;
    private ListNode reverseN(ListNode head, int n) {
        //终止条件
        if (n == 1) {
            lastNext = head.next;
            return head;
        }

        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = lastNext;
        return last;
    }

}
